import java.util.*;
import java.io.*;
public class Graph {
	List<Edge> edges;
	boolean[] vertices;
	String name;

	//#class to contain a graph, list of edges and list of vertices
	public Graph(boolean[] v, List<Edge> e, String n) {
		this.edges = e;
		this.vertices = v;
		this.name = n;
	}

	//#write
	public void write(String filename) {
		try {
			BufferedWriter f = new BufferedWriter(new FileWriter(new
					File(filename)));
			f.write(vertices.length + " " + edges.size() + "\n");
			f.write("\n");
			for (Edge e : edges) {
				f.write(e.get(0) + " " + e.get(1) + "\n");
			}
			f.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	//#load 
	public Graph(String filename) {
		try {
			BufferedReader f = new BufferedReader(new FileReader(new File(filename)));
			edges = new ArrayList();
			name = filename;
			String line = f.readLine();
			vertices = new boolean[Integer.parseInt(line.split(" ")[0])];
			f.readLine();
			while ((line = f.readLine()) != null) {
				edges.add(new Edge(line));
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	//#generates a wheel of n vertices on the perimeter
	static Graph wgen(int v_count) {
		boolean[] v = new boolean[v_count];
		List<Edge> e = new ArrayList();
		for (int i = 0; i < (v_count - 1); i++) {
			e.add(new Edge(i, i + 1));
		}
		e.add(new Edge(v_count - 1, 0));
		for (int i = 0; i < v.length - 1; i++) {
			e.add(new Edge(i, v.length - 1));
		}

		return new Graph(v, e, "wheel (" + v_count + ")");
	}

	//#generates a line of n vertices
	static Graph lgen(int v_count) {
		boolean[] v = new boolean[v_count];
		List<Edge> e = new ArrayList();
		for (int i = 0; i < v_count - 1; i++) {
			e.add(new Edge(i, i + 1));
		}

		return new Graph(v, e, "line (" + v_count + ")");
	}

	//#generates a cycle of n vertices
	static Graph cgen(int v_count) {
		boolean[] v = new boolean[v_count];
		List<Edge> e = new ArrayList();
		for (int i = 0; i < v_count - 1; i++) {
			e.add(new Edge(i, i + 1));
		}
		e.add(new Edge(v_count - 1, 0));

		return new Graph(v, e, "cycle (" + v_count + ")");
	}
/*
//#generates a tree on n vertices
//#it does this by generating all possible edges (i.e. Kn) and running the
//#kruskal algorithm on the graph
static Graph tgen(int v_count){
    v = [x for x in range(v_count)]
    e = []
    temp_elist = []
    temp_vlist = []

    for i in range(v_count):
        for j in range (i+1,v_count):
            temp_elist.append((i,j))

    initial = randint(0,len(temp_elist)-1)
    edge = temp_elist[initial]
    e.append(edge)
    temp_elist.remove(edge)
    temp_vlist.append(edge[0])
    temp_vlist.append(edge[1])
    while len(e) != len(v)-1:
        i = randint(0,len(temp_elist)-1)
        edge = temp_elist[i]
        if (temp_vlist.count(edge[0]) > 0) ^ (temp_vlist.count(edge[1]) > 0):
            e.append(edge)
            temp_elist.remove(edge)
            if temp_vlist.count(edge[0]) == 0:
                temp_vlist.append(edge[0])
            if temp_vlist.count(edge[1]) == 0:
                temp_vlist.append(edge[1])

    return Graph(v,e,''.join(["tree (",str(v_count),")"]))
    }
*/

	//#returns a random graph on the specified number of vertices
	static Graph graphgen(int v_count) {
		boolean[] v = new boolean[v_count];
		List<Edge> e = new ArrayList();
		for (int i = 0; i < v_count; i++) {
			for (int j = i + 1; j < v_count; j++) {
				if (Math.random() > 0.5) {
					e.add(new Edge(i, j));
				}
			}
		}

		return new Graph(v, e, "random (" + v_count + ")");
	}

	//#returns a complete bi-partite graph of the given sizes
	static Graph kkgraphgen(int k1, int k2) {
		boolean[] v = new boolean[k1 + k2];

		List<Edge> e = new ArrayList();
		for (int i = 0; i < k1; i++) {
			for (int j = k1; j < k1 + k2; j++) {
				e.add(new Edge(i, j));
			}
		}
		return new Graph(v, e, "bipartite (" + k1 + "," + k2 + ")");
	}

	//#returns a complete graph of the given size
	static Graph kgraphgen(int v_count) {
		boolean[] v = new boolean[v_count];
		List<Edge> e = new ArrayList();
		for (int i = 0; i < v_count; i++) {
			for (int j = i + 1; j < v_count; j++) {
				e.add(new Edge(i, j));
			}
		}
		return new Graph(v, e, "Complete (" + v_count + ")");
	}


//#this is our predicate for determining if a set is a valid matching

	//#it looks for vertices that occur multiple times in an edge set        
	boolean isMatching(Collection<Edge> e_set) {
		vertices = new boolean[vertices.length];
		for (Edge e : e_set) {
			if (vertices[e.get(0)]) {
				return false;
			}
			vertices[e.get(0)] = true;

			if (vertices[e.get(1)]) {
				return false;
			}
			vertices[e.get(1)] = true;
		}
		return true;
	}
}
